1. Field of the Invention
The present invention relates to a device and method for. decoding data and, more particularly, to a reduced-state device and method for decoding data by generating accumulated conditional probabilities (ACPs) for certain states out of all possible states of an encoder.
2. Description of Related Art
A conventional convolutional encoder encodes information bits using a shift register and a plurality of adders. FIG. 1 shows a schematic diagram of a conventional xc2xd rate convolutional encoder. As shown therein, the conventional convolutional encoder 100 includes a shift register 11 composed of a plurality of memory units M0-M7 connected in series to each other, and first and second adders 10 and 12 coupled to the shift register 11 for generating first and second coefficients C0 and C1. Each of the memory units M0-M7 is a one-bit memory for storing a bit input thereto while shifting the bit already stored therein to a next one-bit memory.
Since there are 8 one-bit memory units M0-M7 in the shift register 11 , the shift register 11 has 256 possible states (from state 0 to state 255). The term xe2x80x9cstatexe2x80x9d indicates the content of the shift register 11 at a given time. It is known that the state of the shift register 11 is an even state if the arriving information bit (i.e., the bit ready to be input to the first memory unit M0) of the previous state of the shift register 11 is zero, or an odd state if the arriving information bit of the previous state of the shift register 11 is one.
An operation of the conventional convolutional encoder 100 of FIG. 1 is as follows. Information bits to be encoded are input to the first memory unit M0 one bit at a time. A block of information bits (e.g., 196 bits) are typically processed at one time. Each new information bit input to the encoder 100 is pushed into the first memory unit M0 of the shift register 11 as the previous content of the first memory unit M0 is shifted to the second memory unit M1, the previous content of the second memory unit M1 to the third memory unit M2, the previous content of the third memory unit M2 to the fourth memory unit M3, and so forth. A controller (not shown) generates a clock signal to shift the bits of the memory units M0-M7 at a predetermined time interval.
The first adder 10 adds the arriving information bit of the shift register 11 with bits stored in the memory units M0, M1, M2, M4, M6, and M7 to generate the first coefficient C0. The second adder 12 adds the arriving information bit with bits stored in the memory units M1, M2, M3 and M7 to generate the second coefficient C1. According to this process, as one bit of information data is input to the encoder 100, a pair of coefficients C0 and C1 are output from the encoder 100 as encoded data. Hence, the encoder 100 has the xc2xd process rate. Although the conventional xc2xd rate convolutional encoder 100 has been described above, encoders having other process rates, e.g., {fraction (1/3, 2/3)}, and others, are also known in the art.
The first and second coefficients C0 and C1 (encoded data) generated by the encoder 100 pass through communication channels to other encoders/decoders. During this process, however, the encoded data suffer from bit corruption and become less reliable. For example, as the encoded data pass through communication channels, certain zero (xe2x80x9c0xe2x80x9d) bits may change to one (xe2x80x9c1xe2x80x9d) bits and vice versa, such that corrupted coefficients CC0 and CC1 are transmitted as encoded data, and are decoded by a conventional convolutional decoder.
To decode the corrupted coefficients CC0 and CC1, a conventional convolutional decoder assumes all possible states of the shift register 11 of the encoder 100, and attempts to determine what the original, uncorrupted coefficients C01 and C1 are. If the original coefficients C0 and C1 output from the encoder 100 can be determined, then accurate input data (i.e., arriving information bits of the encoder 100) can be recovered as decoded data.
FIG. 2 shows a block diagram of such a conventional convolutional decoder 200 for decoding encoded data, such as, corrupted coefficients CC0 and CC1. The decoder 200 includes a state counter 20, a previous state locator 22, first and second encoders 24A and 24B, a modulo 2 unit 26, first and second quantizers 28A and 28B, first and second adders 30A and 30B, a maximum selector 32, a memory unit 34, and a decoding unit 36, connected as shown.
The state counter 20 counts from state 0 to state 255 for each pair of the corrupted coefficients CC0 and CC1 to cover all 256 possible states of the shift register 11 in the conventional encoder 100. The state counting by the state counter 20 is performed based on a clock signal generated from the memory unit 34. Based on each current state count value, the previous state locator 22 determines two possible previous states (i.e., two possible contents of the memory units M0-M7 of the shift register 11 shown in FIG. 1) according to a known process. One of the two possible previous states is output to the first encoder 24A, and the other possible previous state is output to the second encoder 24B.
The modulo 2 unit 26 receives the state count value from the state counter 20, and generates 0 or 1 based on each state count value. The 0 and 1 output from the modulo 2 unit 26 represent possible information bits (0 and 1) to be recovered by the decoder 200.
Each of the first and second encoders 24A and 24B receives the bit from the modulo 2 unit 26 and one of the two possible previous states determined by the previous state locator 22 to generate theoretical coefficients TC0 and TC1. For each input to the first and second encoders 24A and 24B, the first encoder 24A generates a pair of first theoretical coefficients TC0 and TC1, and the second encoder 24B generates a pair of second theoretical coefficients TC0 and TC1. This process is repeated for each of the 256 possible states, so that 256 pairs of theoretical coefficients TC0 and TC1 are sequentially output from each of the first and second encoders 24A and 24B.
Each of the first and second quantizers 28A and 28B receives a pair of the theoretical coefficients TC0 and TC1 for each state count value, and encoded data bits (pairs of corrupted coefficients CC0 and CC1) input to the decoder 200. Each of the first and second quantizers 28A and 28B determines, assuming that uncorrupted coefficients C0 and C1 are input to the decoder 200, the conditional probability of each pair of the corrupted coefficients CC0 and CC1 based on the sequentially received pairs of theoretical coefficients TC0 and TC1, and then quantizes the conditional probability into a certain number of levels, e.g., 32 or 64 levels. The quantized values output from each of the first and second quantizers 28A and 28B indicate how well each pair of inputted corrupted coefficients CC0 and CC1 match the 256 pairs of theoretical coefficients TC0 and TC1. Accordingly, the conventional convolutional decoder 100 carries out a full search algorithm by determining conditional probabilities for the entire 256 possible states of the encoder 100.
Whenever a quantized value is output from the quantizers 28A and 28B, each of the first and second adders 30A and 30B adds the current quantized value with the corresponding accumulated quantized value (i.e., ACP) stored in the memory unit 34 to generate updated ACPs. The maximum selector 32 receives two ACPs from the adders 30A and 30B at a given time, compares the two ACPs to each other, and selects the greater one of the two ACPs. The selected ACP is referred to hereinafter as the winning ACP, and the previous state which results in the winning ACP is referred to hereinafter as the winning previous state (PS). The winning ACP and PS are output to the memory unit 34 unit, where the winning ACP replaces the ACP currently stored in a data slot of the memory unit 34 corresponding to the current state count value.
If a block of 196 information bits are processed at one time by the encoder 100, the memory unit 34 must store 0 to 255 possible ACPs and their corresponding PSs for each of the 196 information bits, and must update all 256 ACPs using the outputs of the maximum selector 32. To carry out this process and the process by the decoding unit 36, the memory unit 34 requires a 256xc3x97196 memory array for storing winning PSs in addition to other memory arrays for storing winning ACPs. FIG. 2A shows an example of a 256xc3x97196 memory array 34a of the memory unit 34 for storing winning PSs. As shown therein, the memory array 34a of the memory unit 34 is composed of 256 rows (R0-R255) and 196 columns (C0-C195). Each row number represents the current state value and each column number represents a bit in the 196 informnation bits. For each information bit (i.e., for each column), the memory unit 34 stores in its array 34a the PSs corresponding to the entire 256 possible states. For example, if the current state is zero (i.e., R0), the 196th information bit is being decoded by the decoder 200, and the winning PS for this particular current state has been determined to be three (3) by the maximum selector 200, then the wining PS of 3 is stored in a data slot (R0, C195) of the array 34a. 
Once all the slots in the array 34a are filled, the decoding unit 36 begins to recover the original information bits using the array 34a. The decoding unit 36 first retrieves the winning PS of 3 from the slot (R0, C195) of the array 34a. Since the winning PS equals 3, the decoding unit 36 goes to row R3 in the next column, C194, and retrieves the winning PS of 1 therefrom. Since the winning PS here equals 1, the decoding unit 36 goes to row R1 in the next column, C193, and retrieves the winning PS of 255 therefrom. Since the winning PS now equals 255, the decoding unit 36 goes to row R255 in the next column, C192, and retrieves the winning PS of 62 therefrom. This process is repeated until the last column C0 is searched. As a result of this retrieval process, 196 integers are sequentially collected by the decoding unit 36. Depending on whether each of the 196 integers is an odd number or an even number, zero (0) or one (1) bit is output from the decoding unit 36 as decoded data representing the original 196 information bits.
As discussed above, conventional decoders require a large memory array (e.g., 256xc3x97196) for storing PSs for all possible states of an encoder. Often, however, it is economically infeasible to employ such a large memory array in a decoder. Furthermore, as time passes, the size of one data block and the number of possible states tend to increase, requiring a much larger memory. But, even if a large memory can be used in the system, a full search algorithm carried out by the conventional convolutional decoders is extremely time consuming because ACPs must be calculated for all possible states of an encoder.
The present invention is directed to a reduced-state device and method for decoding data that uses less memory for storing winning previous states (PSs) associated with accumulated conditional probabilities (ACPs) because less ACPs are generated. The reduced-state device and method select only certain current states from all possible states of an encoder for each encoded data based on a control signal, and generate ACPs for the selected current states. For each non-selected current state, a predetermined quantized value (PQV) is output. The ACPs and the PQV are compared with a threshold value. If the ACP/PQV is greater than or equal to the threshold value, a PS associated with such ACP/PQV is stored in a first memory array. A second memory array stores the positional information of the first memory array in which the winning PS is stored. From each column of the first memory array, one of the values stored therein is selected based on the value selected from the previous column. These selected values are converted into a 0 or 1 bit, and the converted data bits are output as decoded data. Accordingly, the present invention generates ACPs only for certain states out of all possible states and thus, requires less memory for storing PSs associated with the ACPs. Furthermore, the present invention provides a faster decoding process since a reduced number of states are searched to generate decoded data.